// function binarySearch(nums, target) {
//   let left = 0, right = nums.length - 1;
//   while(left <= right) {
//     let mid = parseInt(left + (right - left) / 2);
//     if (nums[mid] == target) { 
//       return mid;
//     } else if (nums[mid] < target) {
//       left = mid + 1;
//     } else if (nums[mid] > target){
//       right = mid - 1;
//     }
//   }
//   return -1;
// }

// const nums = [-1,0,3,5,9,12], target = 9;
// console.log(binarySearch(nums, target));

// function leftBound(nums, target) {
//   let left = 0, right = nums.length - 1;

//   while(left <= right) {
//     let mid = parseInt(left + (right - left) / 2);
//     if (nums[mid] == target) { 
//       right = mid - 1;
//     } else if (nums[mid] < target) {
//       left = mid + 1;
//     } else if (nums[mid] > target) {
//       right = mid - 1;
//     }
//   }
  
//   if (left >= nums.length || nums[left] != target) {
//     return -1;
//   }

//   return left;
// }
// const nums2 = [1,2,2,2,3], target2 = 2;
// console.log(leftBound(nums2, target2))

// function rightBound(nums, target) {
//   let left = 0, right = nums.length - 1;

//   while(left <= right) {
//     let mid = parseInt(left + (right - left) / 2);
//     if (nums[mid] == target) { 
//       left = mid + 1;
//     } else if (nums[mid] < target) {
//       left = mid + 1;
//     } else if (nums[mid] > target) {
//       right = mid - 1;
//     }
//   }
  
//   if (right < 0 || nums[right] != target) {
//     return -1;
//   }

//   return right;
// }

// const nums3 = [1,2,2,2,3], target3 = 2;
// console.log(rightBound(nums3, target3))

// var permute = function(nums) {
//   const res = [], path = [];
  
//   function backtracking(n, k, used) {
//       if(path.length === k) {
//           res.push(Array.from(path));
//           return;
//       }
//       for (let i = 0; i < k; i++ ) {
//           if(used[i]) continue;
//           path.push(n[i]);
//           used[i] = true; // 同支
//           backtracking(n, k, used);
//           console.log(used, path, 'path')
//           path.pop();
   
//           used[i] = false;
//       }

//   }
//   backtracking(nums, nums.length, []);
//   return res;
// };
// console.log(permute([1,2,3]))

// var solveNQueens = function(n) {
//   function isValid(row, col, chessBoard, n) {

//       for(let i = 0; i < row; i++) {
//           if(chessBoard[i][col] === 'Q') {
//               return false
//           }
//       }

//       for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
//           if(chessBoard[i][j] === 'Q') {
//               return false
//           }
//       }

//       for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
//           if(chessBoard[i][j] === 'Q') {
//               return false
//           }
//       }
//       return true
//   }

//   function transformChessBoard(chessBoard) {
//       let chessBoardBack = [];
//       chessBoard.forEach(row => {
//           let rowStr = '';
//           row.forEach(value => {
//               rowStr += value;
//           });
//           chessBoardBack.push(rowStr);
//       })

//       return chessBoardBack;
//   }

//   let result = []
//   function backtracing(row,chessBoard) {
//       if(row === n) {
//           result.push(transformChessBoard(chessBoard))
//           return
//       }
//       for(let col = 0; col < n; col++) {
//           if(isValid(row, col, chessBoard, n)) {
//               chessBoard[row][col] = 'Q'
//               backtracing(row + 1,chessBoard);
//               console.log(chessBoard, 'chessBoardBack');
//               chessBoard[row][col] = '.'
//           }
//       }
//   }
//   let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'));
//   console.log(chessBoard, 'chessBoard');
//   backtracing(0,chessBoard)
//   return result;
// };
// const n = 4;
// console.log(solveNQueens(n));

// var permute = function(nums) {
//   const res = [], path = [];
  
//   function backtracking(n, k, used) {
//       if(path.length === k) {
//           res.push(Array.from(path));
//           return;
//       }
//       for (let i = 0; i < k; i++ ) {
//           if (used[i]) continue;
//           if (i - 1 >= 0 && nums[i - 1] == nums[i] && !used[i - 1]) { // 避免产生重复的排列
//             continue;
//           }
//           path.push(n[i]);
//           used[i] = true; // 同支
//           backtracking(n, k, used);
//           path.pop();
//           used[i] = false;
//       }

//   }
//   backtracking(nums, nums.length, []);
//   return res;
// };

// console.log(permute([1,1,2]));

// function combine(n, k) {
//   let res = [];
//   let path = [];
//   function backtracing(n, k, start) {
//     for(let i = start; i < n - (k - path.length) + 1; i ++) {
//       if (path.length == k) {
//         res.push([...path]);
//         return;
//       }
//       path.push(i);
//       backtracing(n, k, i + 1);
//       path.pop();
//     }
//   }
//   backtracing(n, k ,0);
//   return res;
// }
// console.log(combine(4, 2));

// const maxDepth = (root) => {
//   if (root == null) return 0;
//   const queue = [root];
//   let depth = 1;
//   while (queue.length) {
//       // 当前层的节点个数
//       const levelSize = queue.length;          
//       // 逐个让当前层的节点出列
//       for (let i = 0; i < levelSize; i++) {    
//           // 当前出列的节点
//           const cur = queue.shift();            
//           // 左右子节点入列
//           if (cur.left) queue.push(cur.left);
//           if (cur.right) queue.push(cur.right); 
//       }
//       // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1
//       if (queue.length) depth++;
//   }
//   return depth;
// };

// console.log(maxDepth([3,9,20,null,null,15,7]));
function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}
var mergeTwoLists = function(l1, l2) {
  const prehead = new ListNode(-1);

  let prev = prehead;
  while (l1 != null && l2 != null) {
      if (l1.val <= l2.val) {
          prev.next = l1;
          l1 = l1.next;
      } else {
          prev.next = l2;
          l2 = l2.next;
      }
      prev = prev.next;
      console.log(prev, 'prev');
      console.log(prehead.next, 'prehead')
  }

  if (l1 != null) {
    prev.next = l1;
  }

  if (l2 != null) {
    prev.next = l2;
  }

  // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
  // prev.next = l1 === null ? l2 : l1;
  return prehead.next;
};

const l1 = {val: 1,next: {val: 2, next: {val: 4, next: null}}}, l2 = {val: 1,next: {val: 3, next: {val: 4, next: null}}};
// const l1 = [1,2,4], l2 = [1,3,4]
console.log(mergeTwoLists(l1, l2), 999);

var hasCycle = function(head) {
  // 快慢指针初始化指向 head
  let slow = head;
  let fast = head;
  // 快指针走到末尾时停止
  while (fast && fast.next) {
    // 慢指针走一步，快指针走两步
    slow = slow.next;
    fast = fast.next.next;
    // 快慢指针相遇，说明含有环
    if (slow == fast) {
      return true;
    }
  }
  // 不包含环
  return false;
};
const l3 = {val: 3,next: {val: 2, next: {val: 0, next: {val: 4, next: null}}}};
console.log(hasCycle(l3));

